package com.ls.sort_algorithm;

import java.util.Arrays;

/**
 * 中轴值不意味着这个值始终在中间
 */
public class QuickSort {


    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();

        int[] arr = {3, 7, 9, -1, 16, 1, -2, 10, 11};
//        int[] arr = {-9,78,0,23,-10,70};

        quickSort.quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }


    /**
     * @param arr
     * @param left  最左边的索引
     * @param right 最右边的索引
     */
    public void quickSort(int[] arr, int left, int right) {
        int l = left;
        int r = right;

        int pivot = arr[(left + right) / 2];//中轴值
        int temp = 0;
        //如果l==r 说明只有一个数,
        while (l < r) {

            //从中轴左边开始找,找到比中轴值小的记录其位置(如果没有就指向中轴值)
            while (arr[l] < pivot) {
                l++;
            }

            while (arr[r] > pivot) {
                r--;
            }
            //保证,左索引在右索引的左边
            if (l >= r) {
                break;
            }
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //使整个循环前进[如果一边的值等于中轴值,那么这边就不动了,移动另一边]
            if (arr[l] == pivot) {
                r--;
            }
            if (arr[r] == pivot) {
                l++;
            }

        }
        System.out.println(l + "  " + r);

        //结束一次排序后,左右必定相等[不断移位] 而他们的值就是中轴值,
        // 最后只有一个数的时候l,r继续移位,在下面if (left < r) (right > l)作为退出递归条件,在此形成这个条件
        if (l == r) {
            //相互移位,中间空出的值是已经确定位置的中轴值
            l++;
            r--;
        }
        //如果左右相等说明只有一个数,就不用排了
        if (left < r) {
            quickSort(arr, left, r);
        }
        if (right > l) {
            quickSort(arr, l, right);
        }
    }

    /**
     * @param arr
     * @param left  最左边的索引
     * @param right 最右边的索引
     */
    public void quickSort2(int[] arr, int left, int right) {
        int l = left;
        int r = right;

        int pivot = arr[(left + right) / 2];//中轴值
        int temp = 0;
        //如果l==r 说明只有一个数,
        while (l < r) {


            //从中轴左边开始找,找到比中轴值小的记录其位置(这个有可能找到中轴右边)
            while (arr[l] < pivot) {
                l++;
            }
            while (arr[r] > pivot) {
                r--;
            }


            //保证,左索引在右索引的左边
            if (l <= r) {
                //可能会把中轴位置的值交换
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
                //继续推进
                r--;
                l++;
            }

        }

        //如果 l == r ,必须l++,r++,否则出现栈溢出
        if (l == r) {
            l++;
            r--;
        }
        if (left < r) {
            quickSort(arr, left, r);
        }
        if (right > l) {
            quickSort(arr, l, right);
        }
    }



}
